<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-15">
<title>Merging newer versions of Valgrind into Fjalar</title>
</head>
<body>
<h1>Merging newer versions of Valgrind into Fjalar</h1>


<p>
Fjalar is built as a tool on top of Valgrind, and it it also
contains a sizable amount of code from Memcheck, another Valgrind tool.
When new versions of Valgrind and Memcheck are released, Fjalar should be
updated to incorporate the Valgrind/Memcheck changes.
This document tells you how to do so.
</p>

<p>
Conceptually, this is two separate updates: (1) Updating 
the underlying copy of Valgrind to the newer version of Valgrind, and (2)
Updating the memcheck code contained in Fjalar to the newer version
of Memcheck.  Due to very tight dependence of the memcheck code
on Valgrind, the changes should be done simultaneously.
</p>

<p>
The update of the underlying copy of Valgrind can usually be done almost
automatically.
Updating the memcheck code often involves manual work, due to substantial
modifications to the memcheck code that is incorporated in Fjalar.
The more frequent
the merges are, the easier they will be to do.  Monthly, at the very least, is
recommended.
</p>

<p>Contents:</p>
<!-- start toc.  do not edit; run html-update-toc instead -->
    <ul>
      <li><a href="#Getting_Started">1. Getting Started</a>
        <ul>
          <li><a href="#checkout_fjalar">1.1 Obtain a copy of the Fjalar source</a></li>
          <li><a href="#current_fjalar">1.2 Ensure your copy of Fjalar is up to date</a></li>
          <li><a href="#current-valgrind">1.2 Obtain a current copy of the Valgrind Source</a></li>
          <li><a href="#old-valgrind">1.3 Obtain a copy of the Valgrind and VEX source corresponding to the Fjalar version</a></li>
        </ul></li>
      <li><a href="#Creating_the_diffs">2. Creating the diffs</a>
        <ul>
          <li><a href="#valgrind-diff">2.1 Coregrind and Memcheck Diff</a></li>
          <li><a href="#pag-coregrind-diff">2.2 PAG Coregrind Diff</a></li>
        </ul></li>
      <li><a href="#Merging_the_changes">3. Merging the changes</a>
        <ul>
          <li><a href="#coregrind-merge">3.1 Coregrind Merge</a></li>
          <li><a href="#coregrind-conflicts">3.2 Coregrind Conflicts</a></li>
          <li><a href="#memcheck-merge">3.3 Memcheck Merge</a></li>
          <li><a href="#memcheck-conflicts">3.4 Memcheck Conflicts</a></li>
          <li><a href="#Updating_Fjalar_Kvasir">3.5 Updating Fjalar/Kvasir</a></li>
        </ul></li>
      <li><a href="#Compiling">4. Compiling and Testing</a>
        <ul>
          <li><a href="#compiling_fjalar">4.1 Compiling Fjalar</a></li>
          <li><a href="#testing_fjalar">4.2 Testing Fjalar</a></li>
          <li><a href="#documenting_changes">4.3 Documenting Changes</a></li>
        </ul></li>
      <li><a href="#Committing">5. Committing</a>
        <ul>
          <li><a href="#cvs-add-remove">5.1 Tell CVS about files that were added or removed</a></li>
          <li><a href="#commit-commands">5.2 Commit commands</a></li>
        </ul></li>
      <li><a href="#Valgrind_modifications">Appendix A: Valgrind modifications</a></li>
      <li><a href="#Memcheck_modifications">Appendix B: Memcheck modifications</a></li>
      <li><a href="#New_IR">Appendix C: Supporting new VEX IR Instruction</a></li>
    </ul>
<!-- end toc -->

<hr>

<h2 id="Getting_Started">1. Getting Started</h2>

<p>The instructions assume you use bash or sh as your shell.
If you use a different shell, adjust the instructions as necessary.</p>

<p>You need to obtain 2 copies of Valgrind: the most recent, and the
one the current version of Fjalar is based on.</p>


<p>
<b>Note:</b>
As of 9/13/2009, the tests pass on a CSAIL PAG machine (Debian), but do not
run on a UW CSE machine (Fedora) nor on Ubuntu 9.04.
</p>


<h3 id="checkout_fjalar">1.1 Obtain a copy of the Fjalar source </h3>

<p>
First, check out Daikon and Fjalar from CVS.  You may skip this
if you already have a copy of invariants/valgrind-3
checked out.
</p>

<!--
 If your current checkout contains any layout changes to the kvasir
 directory, it may be more convenient to move your current checkout and
 follow the below directions.
-->

<p>
(From a PAG machine)
<pre>
  cvs -d $pag/projects/invariants/.CVS co invariants
  cd invariants
  export $INV=`pwd`
  cvs -d $pag/projects/invariants/.CVS co valgrind-3
</pre>

<h3 id="current_fjalar">1.2 Ensure your copy of Fjalar is up to date </h3>

<p>
First, update your checkout.
</p>

<pre>
  cd $INV
  cvs -q update
   cd valgrind-3
  cvs -q update
</pre>

<p>
Ensure there are no local changes.
</p>

<pre>
  cd $INV
  cvs -q diff --brief
  cd valgrind-3
  cvs -q diff --brief
</pre>

<p>
The diff commands should produce no output.
If there are any differences, commit them, then start over from the beginning.
</p>

<p>
Re-compile Fjalar, then run the tests.  (The tests take about 20 minutes.)
</p>

<pre>
  cd $INV/valgrind-3
  ./auto-everything.sh
  cd $INV/tests/kvasir-tests 
  make nightly-summary-w-daikon
</pre>

<p>
The tests should pass.
If any tests fail, fix them, then start over from the beginning.
</p>


<h3 id="current-valgrind">1.2 Obtain a current copy of the Valgrind Source </h3>

<pre>
  cd $INV
  svn co svn://svn.valgrind.org/valgrind/trunk valgrind-new </pre>

<p>Additional information about working with the Valgrind repository can be found at: <a href="http://www.valgrind.org/downloads/repository.html">Valgrind: Code Repository</a></p>

<h3 id="old-valgrind">1.3 Obtain a copy of the Valgrind and VEX source corresponding to the Fjalar version </h3>

<pre>
  cd $INV
  source valgrind-3/valgrind/REVISION
  svn co -r $VALGRIND_REVISION svn://svn.valgrind.org/valgrind/trunk valgrind-old
  cd valgrind-old
  svn update -r $VEX_REVISION VEX </pre>

<p>The VEX update is necessary because the VEX instrumentation libraries Valgrind is built on is stored in a separate
SVN repository. A Valgrind checkout will always check out the most recent
version of the VEX source. This is fine for when we checked out the current
Valgrind source, however, we'll want the same version used in the Fjalar
repository for the copy that will be diffed.</p>

<hr>
<h2 id="Creating_the_diffs">2. Creating the diffs</h2>

<p>Create diffs showing what the Valgrind maintainers have changed since
  the last time Valgrind code was merged into Fjalar.
  Two separate diffs will be created:  one for Memcheck and one for
  everything else (which we'll call "Coregrind", and which includes VEX).</p>

<h3 id="valgrind-diff">2.1 Coregrind and Memcheck Diff</h3>
<pre>
  cd $INV
  \rm -f coregrind.patch memcheck.patch
  diff -ur --unidirectional-new-file -x 'Makefile.in' -x '.cvsignore' -x inst -x '.svn' -x CVS valgrind-old valgrind-new > coregrind.patch
  diff -ur --unidirectional-new-file -x 'Makefile.in' -x '.cvsignore' -x '.svn' -x CVS -x docs -x tests -x perf valgrind-old/memcheck valgrind-new/memcheck > memcheck.patch</pre>


<h3 id="pag-coregrind-diff">2.2 PAG Coregrind Diff</h3>

<p> Generate a diff containing PAG changes to coregrind. This will not be used for any automated patching, so we will be excluding a lot more irrelevant files. Also the PAG repository contains many of the automake/autoconf generated files to simplify things for the end users, these also need to be omitted for a cleaner diff. The below command should create a diff containing the relevant PAG changes to the Valgrind source code.
</p>

<pre>
  cd $INV
  \rm -f coregrind-PAG.diff memcheck-PAG.diff
  diff -ur --unidirectional-new-file -x 'Makefile.in' -x '.cvsignore' -x inst -x '.svn' -x CVS -x fjalar valgrind-old valgrind-3/valgrind/ > coregrind-PAG.diff
  diff -ur --unidirectional-new-file -x 'Makefile.in' -x '.cvsignore' -x '.svn' -x CVS -x docs -x tests -x perf valgrind-old/memcheck valgrind-3/valgrind/fjalar > memcheck-PAG.diff
</pre>

<hr>

<h2 id="Merging_the_changes">3. Merging the changes</h2>

<h3 id="coregrind-merge">3.1 Coregrind Merge</h3>
<p>Now we can merge the changes from the created diffs. The coregrind patch should apply with very little conflicts.</p>

<p> It can be difficult to undo a patch operation, so you should first attempt a dry run. </p>

<pre>
  cd $INV/valgrind-3/valgrind
  patch -p1 < $INV/coregrind.patch --dry-run</pre>

<p>If the
patch fails, it might be indicative of problems in the above diffing.</p>

<p>When you are ready to apply the patch run:</p>
<pre>
  cd $INV/valgrind-3/valgrind
  patch -p1 < $INV/coregrind.patch</pre>

<h3 id="coregrind-conflicts">3.2 Coregrind Conflicts</h3>

<p>Handle any conflicts.  They are listed in the patch
  output, or run this command:</p>

<pre>
  find -name '*.rej'
</pre>

<p>
For every change in the file you will need to examine both the changed code
as well as our original code and determine if it needs to be hand merged or
if the change is not relevant. It is useful to refer to
<tt>coregrind-PAG.diff</tt> during this process.
Remove the <tt>.rej</tt> and <tt>.orig</tt> files as you go, so that
finally the <tt>find</tt> command produces no output.
</p>


<h3 id="memcheck-merge">3.3 Memcheck Merge</h3>

<pre>
  cd $INV/valgrind-3/valgrind/fjalar
  patch -p2 < $INV/memcheck.patch --dry-run</pre>

<p> If the patch output looks sane, continue with the actual merge </p>

<pre>
  cd $INV/valgrind-3/valgrind/fjalar
  patch -p2 < $INV/memcheck.patch </pre>


<h3 id="memcheck-conflicts">3.4 Memcheck Conflicts</h3>

<p>Handle any conflicts.  They are listed in the patch
  output, or run this command:</p>

<pre>
  find -name '*.rej'
</pre>

<p>
For every change in the file you will need to examine both the changed code
as well as our original code and determine if it needs to be hand merged or
if the change is not relevant.</p>

<p>
Our changes to Memcheck are much more substantial than our changes to
Coregrind.</p>

<p>
The largest modification to memcheck is in mc_translate.c and special care
should be made to ensure it is present and up to date.  MC_(instrument)
handles the instrumentation of calls for DynComp. It is primarily contained
in a switch statement; each case handles one VEX instruction type, and the
body contains both the original code for memcheck and also the code for
dyncomp.  After the update, you should double-check that each clause
contains corresponding code:  any changes to the memcheck versions are
reflected in the dyncomp versions, and any new clause has a dyncomp version.
</p>


<h3 id="Updating_Fjalar_Kvasir">3.5 Updating Fjalar/Kvasir</h3>

<p>Additionally Fjalar/Kvasir need to be updated to properly handle any changes in Valgrind API/functionality.  
For the most part Valgrind maintains a relatively stable interface to its tools. Any tool-visible changes
should be noted in the change logs.</p>

<p>A somewhat more problematic area are changes in the VEX IR. DynComp makes heavy use of the VEX IR, so any
changes in it need to be reflected. Most of the changes to the public VEX IR can be discovered by running the following command:</p>

<pre>
  cd $inv/valgrind-new
  svn log -r ${VEX_REVISION}:HEAD VEX/pub/libvex_ir.h</pre>

<p>
The files with all the VEX IR code for DynComp is located in dyncomp_translate.[ch]. dyncomp_translate.c
is structured primarily into functions of the form <i>expr2tags_[EXPRESSION_TYPE]()</i>. These functions
will  contain a switch for all VEX IR instructions corresponding to the expression type and some
call to a dyncomp tag function. Most often VEX IR changes will be syntactical in nature and will only
involve changing the names of the instructions. If the log indicates that new VEX IR instructions have been
added, they will need to be explicitly supported by DynComp. Please see <a href="#New_IR">Appendix C</a> for
guidelines on supporting new VEX instructions.
</p>


<hr>
<h2 id="Compiling">4. Compiling and Testing</h2>

<p>We must now ensure that the merged code compiles correctly and passes the regression test suite.</p>

<h3 id="compiling_fjalar">4.1 Compiling Fjalar</h3>

<pre>
  cd $INV/valgrind-3
  ./auto-everything.sh </pre>

<p> The auto-everything shell script should autogen the config
  and Makefiles and compile Fjalar.  Fix any compilation errors.</p>

<h3 id="testing_fjalar">4.2 Testing Fjalar</h3>
<p>The regression suite is located in the tests/kvasir-tests directory.
It can be run using the following commands, which take about 20 minutes:</p>

<pre>
  cd $INV/tests/kvasir-tests 
  make nightly-summary-w-daikon</pre>

<p>The test suite should pass without modification.</p>

<h3 id="documenting_changes">4.3 Documenting Changes</h3>

<p>Any user-visible changes should be documented in <tt>$INV/docs/CHANGES</tt>. Additionally, 
<tt>valgrind-3/valgrind/REVISION</tt> should be updated with the Valgrind and VEX revisions 
that were used for this merge.</p>

<p>The revision for Valgrind can be obtained by:</p>

<pre>
  export VALGRIND_REVISION_NEW=`(cd $INV/valgrind-new; svn info | grep "Last Changed Rev: " | cut -d " " --fields=4)`
  echo $VALGRIND_REVISION_NEW
</pre>

<p>The revision for VEX can be obtained by:</p>

<pre>
  export VEX_REVISION_NEW=`(cd $INV/valgrind-new/VEX; svn info | grep "Last Changed Rev: " | cut -d " " --fields=4)`
  echo $VEX_REVISION_NEW
</pre>


<hr>
<h2 id="Committing">5. Committing</h2>

<p>
If the test suite passes with no errors and all
changes are documented, changes should be committed to the CVS repository.
</p>


<h3 id="cvs-add-remove">5.1 Tell CVS about files that were added or removed</h3>

<p>Tell CVS about files that were created/deleted by the patch:</p>

<pre>
  cd $INV/valgrind-3

  grep -q '^\-\-\-.*1969\-12\-31' $INV/coregrind.patch 
  if [ "$?" == "0" ]; then
    cvs add `grep '^\-\-\-.*1969\-12\-31' $INV/coregrind.patch | cut --fields=1 | cut -d ' ' --fields=2 | perl -p -e 's/^valgrind-old/valgrind/g'`
  fi

  grep -q '^\+\+\+.*1969\-12\-31' $INV/coregrind.patch 
  if [ "$?" == "0" ]; then
    cvs remove `grep '^\+\+\+.*1969\-12\-31' $INV/coregrind.patch | cut --fields=1 | cut -d ' ' --fields=2 | perl -p -e 's/^valgrind-new/valgrind/g'`
  fi

  grep -q '^\-\-\-.*1969\-12\-31' $INV/memcheck.patch
  if [ "$?" == "0" ]; then
    cvs add `grep '^\-\-\-.*1969\-12\-31' $INV/memcheck.patch| cut --fields=1 | cut -d ' ' --fields=2 | perl -p -e 's/^valgrind-old/valgrind/g'`
  fi

  grep -q '^\+\+\+.*1969\-12\-31' $INV/memcheck.patch
  if [ "$?" == "0" ]; then
    cvs remove `grep '^\+\+\+.*1969\-12\-31' $INV/memcheck.patch| cut --fields=1 | cut -d ' ' --fields=2 | perl -p -e 's/^valgrind-new/valgrind/g'`
  fi
</pre>


<h3 id="commit-commands"> 5.2 Commit commands </h3>

<pre>
  cd $INV
  <i># Double-check the diffs &mdash; standard practice before committing</i>
  cvs -q diff -b --brief -N
  <i># If necessary: cvs diff</i>
  <i># Add any other relevant notes to the below.</i>
  cvs commit -m "Valgrind merge from revision ${VALGRIND_REVISION} to ${VALGRIND_REVISION_NEW}.  VEX IR merge from ${VEX_REVISION} to ${VEX_REVISION_NEW}."
  \rm -f coregrind.patch memcheck.patch coregrind-PAG.diff memcheck-PAG.diff
</pre>

<hr>
<h2 id="Valgrind_modifications">Appendix A: Valgrind modifications</h2>

<p>In an effort to aid in determining the appropriate measures to take when merging conflicted files,
this section will provide a list of files modified by us and a brief explanation of the changes.
</p>

<!-- Should I include functions too? -->

<p>The most important set of changes is the addition of extra shadow state in Coregrind and VEX.
The shadow area is an area of memory that Valgrind provides for tools to use. Unfortunately,
it is of a fixed size, and memcheck uses all of it. We've had to increase the size of the
the shadow area.
</p>

<dl>
<dt>$INV/valgrind-3/valgrind/coregrind/pub_core_threadstate.h</dt>
<dd>The declaration of the extra shadow space</dd>
<dt>$INV/valgrind-3/valgrind/coregrind/m_scheduler/scheduler.c</dt>
<dd>An assertion that triggers based on shadow size</dd>
<dt>$INV/valgrind-3/valgrind/VEX/priv/host-generic/reg_alloc2.c</dt>
<dd>memory calculation using the shadow size</dd>
</dl>

<p> Additionally, we had to modify some of the VEX architecture files to
return information specific to the x86 platform. </p>

<dl><dt>$INV/valgrind-3/valgrind/VEX/priv/guest-x86/ghelpers.c</dt>
<dt>$INV/valgrind-3/valgrind/VEX/pub/libvex.h</dt>
<dd>Addition of primary/secondary integer return registers to the guest state</dd>
<dt>$INV/valgrind-3/valgrind/coregrind/m_machine.c</dt>
<dt>$INV/valgrind-3/valgrind/include/pub_tool_machine.h</dt>
<dd>Tool-visible functions to access the primary/secondary integer return registers</dd>
</dl>

<p> Finally, we had to extend Valgrind's implementation of the C library with a few extra
functions. </p>

<dl><dt>$INV/valgrind-3/valgrind/coregrind/m_libcfile.c</dt>
<dt>$INV/valgrind-3/valgrind/include/pub_tool_libcfile.h</dt>
<dd>Addition of extra libc functions</dd>
</dl>
<hr>

<h2 id="Memcheck_modifications">Appendix B: Memcheck modifications</h2>

<p>The modifications made to memcheck are more organizational in nature. A few functions from
mc_main.c and mc_translate.c have been made non-static. An extra header has also been created
and filled with their signatures for use by Fjalar.</p>

<p>Other modifications include:</p>
<dl>
<dt>$INV/valgrind-3/valgrind/fjalar/mc_malloc_wrappers.c</dt>
<dd>Calls to DynComp functions for memory operations.</dd>
<dt>$INV/valgrind-3/valgrind/fjalar/mc_main.c</dt>
<dd>Run-time arguments and versioning information for Kvasir to replace the default memcheck ones</dd>
<dt>$INV/valgrind-3/valgrind/fjalar/mc_translate.c</dt>
<dd>In memcheck's instrumentation block, duplicate each case for DynComp.</dd></dl>

<hr>

<h2 id="New_IR">Appendix C: Supporting new VEX IR Instruction</h2>

<p>It is recommended that you acquaint yourself with the VEX IR by reading through:
</p>

<dl>
<dt>$INV/valgrind-3/valgrind/VEX/pub/libvex.h</dt>
<dt>$INV/valgrind-3/valgrind/VEX/pub/libvex_ir.h</dt>
</dl>

<p>In addition to being the primary headers for the VEX library, the above 2 files represent the majority of
the public documentation on VEX. <!-- Is it possible for us to make the VEX .pdf to PAG members? -->Valgrind's translation pipeline consists of the following:
</p>

<pre>  Native assembly -> Pre-instrumented VEX IR -> Post-Instrumented VEX IR -> Final assembly</pre>

<p>Valgrind begins by translating the entirety of an assembly basic block into VEX IR. Valgrind then allows tools
to instrument examine the translated basic block and insert their own instrumentation. Valgrind finishes by translated
the instrumented IR back into the machine's native assembly.
</p>

<p>In order to keep track of comparabilities, DynComp instruments almost every VEX IR instruction type.
Any added instructions will likely need to be supported by DynComp. In general DynComp's functionality parallels Memcheck's,
so the best starting point for implementing support for a new instruction would be to mirror Memcheck's implementation.
DynComp's layout is very similar to Memcheck's, so mirroring functionality should be fairly straightforward.
It is, however, very unlikely that a new instruction type will be added as the VEX IR is a relatively mature
instruction set and has been in use for almost 9 years at the time of this writing.
</p>

<p>Another type of addition that will need to be supported are added "IR Expressions." Most VEX IR instructions are implemented as
a set of IR Expressions - Take the following IR instructions for example:
</p>

<pre>
t5 = Add32(t12,0x8:I32)
t10 = CmpLE32S(t2,0x21:I32)
</pre>

<p>
The above 2 IR Instructions are of the type PUT and they store the result of an IR Expression into a temporary. These instructions consist of
the destination temporary, an IR Expression, which conceptually is the operation to be formed, and the arguments to the expression. Most IR
Instructions will have a similar format. DynComp is particularly interested
in analyzing all possible IRExpressions.
</p>
<pre>$INV/valgrind-3/valgrind/kvasir/fjalar/kvasir/dyncomp_translate.c</pre>
<p>contains the following set of functions for processing IRExpressions.
</p>

<dl>
<dt><b>IRExpr* expr2tags_DC ( DCEnv* dce, IRExpr* e )</b></dt>
<dd> The main expression handling function. Contains a switch which is responsible for
delegating expression handling to one of hte other functions</dd>
<dt><b>IRExpr* expr2tags_Qop_DC(...)</b> </dt>
<dd> Responsible for the handling of expressions which take 4 arguments. </dd>
<dt><b>IRExpr* expr2tags_Triop_DC(...)</b> </dt>
<dd> Responsible for the handling of expressions which take 3 arguments. </dd>
<dt><b>IRExpr* expr2tags_Binop_DC(...)</b> </dt>
<dd> Responsible for the handling of expressions which take 2 arguments. </dd>
<dt><b>IRExpr* expr2tags_Unop_DC(...)</b> </dt>
<dd> Responsible for the handling of expressions which take 1 argument. </dd>
<dt><b>IRExpr* expr2tags_Ldle_DC(...)</b> </dt>
<dd> Responsible for the handling of load expressions</dd>
<dt><b>IRExpr* expr2tags_CCall_DC(...)</b> </dt>
<dd> Responsible for the handling of calls to pure functions.</dd>
<dt><b>IRExpr* expr2tags_Mux0X_DC(...)</b> </dt>
<dd> Responsible for the handling of multiplexing expressions</dd>
</dl>


<p>
If a new IR Expressions is added, it will need to be handled by one of the above functions. The easiest way to implement it will be to base it on
the implementation of an existing instruction. Alternatively, it should be straightforward to mimic Memcheck's handling of the expression.
</p>

<hr>

<address></address>
<!-- hhmts start -->Last modified: June 4, 2015<!-- hhmts end -->
</body> </html>

<!--  LocalWords:  Memcheck memcheck Kvasir diffs Coregrind Diff valgrind PAG
 -->
<!--  LocalWords:  cvs pag co cd svn kvasir diffed diff ur cvsignore inst drd
 -->
<!--  LocalWords:  auxprogs cachegrind callgrind exp ptrcheck helgrind massif
 -->
<!--  LocalWords:  coregrind perf automake autoconf fjalar aclocal config supp
 -->
<!--  LocalWords:  depcomp mkinstalldirs diffing rej mc DynComp dyncomp ch expr
 -->
<!--  LocalWords:  autogen'ing daikon html libc malloc versioning memcheck's rm
 -->
<!--  LocalWords:  EDT INV pwd grep autogen Valgrind's perl fi Makefiles
 -->

<!--
Local Variables:
time-stamp-start: "^.![-]- hhmts start [-]-.Last modified: "
time-stamp-end: "<.[-]- hhmts end [-]-.$"
time-stamp-format: "%:b %:d, %:y"
time-stamp-line-limit: -50
End:
-->
